Logical Equivalences
- Implication Equivalence: \(P → Q \equiv ¬P ∨ Q\)
- Biconditional Equivalence: \(P ↔ Q \equiv (P → Q) ∧ (Q → P) \equiv (¬P ∨ Q) ∧ (P ∨ ¬Q)\)
- Identity Law: \(p \lor 0 \equiv p\)
- Identity Law: \(p \land 1 \equiv p\)
- Complement Law: \(p \lor \neg p \equiv 1\)
- Complement Law: \(p \land \neg p \equiv 0\)
- Idempotent Law: \(p \land p \equiv p\)
- Idempotent Law: \(p \lor p \equiv p\)
- Double Negation Law: \(\neg(\neg p) \equiv p\)
- Associative Law: \((p \lor q) \lor r \equiv p \lor (q \lor r)\)
- Distributive Law: \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
- Distributive Law: \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
- De Morgan’s Law: \(\neg(p \land q) \equiv \neg p \lor \neg q\)
- De Morgan’s Law: \(\neg(p \lor q) \equiv \neg p \land \neg q\)
- Bi-implication Equivalence: \(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\)
- Adjacency Law: \(p \lor (\neg p \land q) \equiv p \lor q\)
- Simplification Law: \((p \lor q) \land (p \lor \neg q) \equiv p\)
- Contrapositive Equivalence: \(A \to B \equiv \neg B \to \neg A\)
Predicate Logic
- De Morgan’s Law for Universal Quantifier: \(\neg \forall x P(x) \equiv \exists x \neg P(x)\)
- De Morgan’s Law for Existential Quantifier: \(\neg \exists x P(x) \equiv \forall x \neg P(x)\)
- Restricted Universal: \(∀x∈A P(x) ≡ ∀x (A(x) → P(x))\)
- Restricted Existential: \(∃x∈A P(x) ≡ ∃x (A(x) ∧ P(x))\)
Set Theory
- Complement: \(\overline{A} = U \setminus A\)
- Difference: \(A \setminus B = A \cap \overline{B}\)
- De Morgan’s Law: \(\overline{(A \cup B)} = \overline{A} \cap \overline{B}\)
- De Morgan’s Law: \(\overline{(A \cap B)} = \overline{A} \cup \overline{B}\)
- Distributive Law: \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
- Cardinality of a Union (Two Sets): \(|A \cup B| = |A| + |B| - |A \cap B|\)
- Cardinality of a Union (Three Sets): \[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \]
- Cardinality of a Set Difference: \(|A \setminus B| = |A| - |A \cap B|\)
- Cardinality of a Cartesian Product: \(|A \times B| = |A| \cdot |B|\)
- Intersection of Cartesian Products: \((A \times C) \cap (B \times D) = (A \cap B) \times (C \cap D)\)
- Intersection of Power Sets: \(P(A) \cap P(B) = P(A \cap B)\)
Proofs and Number Theory
- Definition of an Odd Integer: \(n = 2k + 1\)
- Definition of an Even Integer: \(n = 2k\)
- Sum of First \(n\) Integers: \[ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \]
- Sum of First \(n\) Squares: \[ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \]
- Sum of a Geometric Series: \[ \sum_{i=0}^{n} 2^i = 2^{n+1} - 1 \]
- Fibonacci Recurrence Relation: \(f_n = f_{n-1} + f_{n-2}\)
- Binet’s Formula: \[ f_n = \frac{(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \]
- Sum of First \(n\) Odd-Indexed Fibonacci Numbers: \(f_1 + f_3 + \dots + f_{2n-1} = f_{2n}\)
- Bernoulli’s Inequality: \((1 + x)^n \ge 1 + xn\)
Combinatorics
- Ordered Arrangement with Repetition: \(n^k\)
- Ordered Arrangement without Repetition (Permutation): \[P(n, k) = \frac{n!}{(n-k)!}\]
- Permutation of n distinct items: \(n!\)
- Unordered Arrangement without Repetition (Combination): \[C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\]
- Partitioning into Unordered Groups: \[\frac{C(n, k_1) \times C(n-k_1, k_2) \times \dots}{m!}\]
- Permutations with Repetition (Multinomial Coefficient): \[\frac{n!}{n_1!n_2!\dots n_k!}\]
- Coefficient of \(x^{j}y^{k}\) in \((ax+by)^n\): \[\binom{n}{k} a^{j} b^k\]
- Coefficient of \(x_1^{k_1} \dots x_m^{k_m}\) in \((c_1x_1 + \dots + c_mx_m)^n\): \[\binom{n}{k_1, k_2, \dots, k_m} c_1^{k_1} c_2^{k_2} \dots c_m^{k_m}\]
- Unordered Arrangement with Repetition (Stars and Bars): \[C(n+k-1, k) = \binom{n+k-1}{k}\]
- Solutions to \(x_1 + \dots + x_k = n\) for \(x_i \ge 0\): \[C(n+k-1, k-1) = \binom{n+k-1}{k-1}\]
- Complementary Counting: \(|A| = |Total| - |\overline{A}|\)
Recurrence Relations
- Arithmetic Progression: \(a_n = a_0 + nd\)
- Geometric Progression: \(a_n = a_0 \cdot t^n\)
- Second-Order Recurrence General Solution (Distinct Roots \(p_1, p_2\)): \(a_n = c_1 p_1^n + c_2 p_2^n\)
- Second-Order Recurrence General Solution (Repeated Root \(p\)): \(a_n = (c_1 n + c_2) p^n\)
Relations and Graph Theory
- Total Number of Binary Relations on \(n\) Elements: \(2^{n^2}\)
- Number of Reflexive Relations on \(n\) Elements: \(2^{n(n-1)}\)
- Number of Irreflexive Relations on \(n\) Elements: \(2^{n(n-1)}\)
- Number of Symmetric Relations on \(n\) Elements: \(2^{\frac{n(n+1)}{2}}\)
- Number of Asymmetric Relations on \(n\) Elements: \(3^{\frac{n(n-1)}{2}}\)
- Number of Anti-symmetric Relations on \(n\) Elements: \(2^n \cdot 3^{\frac{n(n-1)}{2}}\)
- Number of Linear Orders on \(n\) Elements: \(n!\)
- Asymmetric Relation Equivalence: Asymmetric \(\iff\) Anti-symmetric \(\land\) Irreflexive
- Non-strict from Strict Order: \(x \leq y \equiv (x < y \lor x = y)\)
- Handshaking Lemma: \(\sum_{v \in V_G} d_G(v) = 2|E_G|\) (the sum of all degrees equals twice the number of edges)
- Number of Edges in Complete Graph \(K_n\): \(|E| = \binom{n}{2} = \frac{n(n-1)}{2}\)
- Degree of Vertices in \(K_n\): Each vertex has degree \(n-1\)
- Degree of Vertices in \(C_n\): Each vertex has degree 2
- Number of Edges in \(C_n\): \(|E| = n\)
- Number of Edges in Complete Bipartite Graph \(K_{n,m}\): \(|E| = nm\)
- Characteristic Property of Trees: A connected graph with \(n\) vertices is a tree if and only if it has exactly \(n-1\) edges
- Number of Edges in a Forest: A forest with \(n\) vertices and \(k\) components has exactly \(n-k\) edges
- Number of Possible Simple Graphs of Order \(n\): \(2^{\binom{n}{2}} = 2^{\frac{n(n-1)}{2}}\) (each potential edge can be present or absent)
- Number of Possible Bipartite Graphs with Sets \(|U|=n\) and \(|V|=m\): \(2^{nm}\) (each potential edge between sets can be present or absent)
Eulerian and Hamiltonian Graphs
- Euler Cycle Condition: A non-trivial connected graph is Eulerian if and only if every vertex has even degree
- Euler Path Condition: A connected graph has an Euler path if and only if it has exactly zero or exactly two vertices with odd degree
- Complete Graph Eulerian: \(K_n\) is Eulerian if and only if \(n\) is odd
- Complete Bipartite Graph Eulerian: \(K_{n,m}\) is Eulerian if and only if both \(n\) and \(m\) are even
- Complete Bipartite Graph Hamiltonian: \(K_{n,m}\) is Hamiltonian if and only if \(n = m \geq 2\)
- Dirac’s Theorem (Sufficient Condition for Hamiltonian): Let \(G\) be a simple graph with \(n \geq 3\) vertices. If \(\deg(v) \geq \frac{n}{2}\) for every vertex \(v\), then \(G\) is Hamiltonian
- Ore’s Theorem (Sufficient Condition for Hamiltonian): Let \(G\) be a simple graph with \(n \geq 3\) vertices. If \(\deg(u) + \deg(v) \geq n\) for every pair of non-adjacent vertices \(u\) and \(v\), then \(G\) is Hamiltonian
Planar Graphs and Colourings
- Euler’s Formula (Planar Graphs): \(v - e + f = 2\), where \(v\) = vertices, \(e\) = edges, \(f\) = faces (including exterior face)
- Edge Bound for Planar Graphs: If \(G\) is a connected planar graph with \(v \geq 3\), then \(e \leq 3v - 6\)
- Edge Bound for Bipartite Planar Graphs: If \(G\) is a connected bipartite planar graph with \(v \geq 3\), then \(e \leq 2v - 4\)
- Face-Edge Inequality (General): \(3f \leq 2e\) (each face has at least 3 edges, each edge borders at most 2 faces)
- Face-Edge Inequality (Bipartite): \(4f \leq 2e\) (bipartite graphs have no triangles, so each face has at least 4 edges)
- Chromatic Number of Complete Graph: \(\chi(K_n) = n\)
- Chromatic Number of Null Graph: \(\chi(O_n) = 1\) (graph with no edges)
- Chromatic Number of Bipartite Graph: \(\chi(G) = 2\) for any non-trivial bipartite graph \(G\)
- Chromatic Number of Odd Cycle: \(\chi(C_{2k+1}) = 3\)
- Chromatic Number of Even Cycle: \(\chi(C_{2k}) = 2\)
- Four Colour Theorem: \(\chi(G) \leq 4\) for any planar graph \(G\)
- Kuratowski’s Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\)